package leetcode.D100.T4;

class Solution {
    // 一刷
    /*public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKthSmallest(nums1, nums2, left, 0, 0) + findKthSmallest(nums1, nums2, right, 0, 0)) / 2;
    }
    private double findKthSmallest(int[] nums1, int[] nums2, int k, int start1, int start2) {
        int len1 = nums1.length-start1, len2 = nums2.length-start2;
        if(len1 == 0 || len2 == 0) {
            return len1 != 0 ? nums1[start1 + k - 1] : nums2[start2 + k - 1];
        }
        if(k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int loc1 = Math.min(nums1.length-1, start1 + (k/2) - 1), loc2 = Math.min(nums2.length-1, start2 + (k/2) - 1);
        if(nums1[loc1] < nums2[loc2]) {
            return findKthSmallest(nums1, nums2, k - (Math.min(k/2, nums1.length)), loc1 + 1, start2);
        } else {
            return findKthSmallest(nums1, nums2, k - (Math.min(k/2, nums2.length)), start1, loc2 + 1);
        }
    }*/

    // 二刷
    /*public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int left = (len1 + len2 + 1) / 2, right = (len1 + len2 + 2) / 2;  // 第k大的数，k最小为1（不是0）
        return (findKthSmallest(nums1, nums2, 0, 0, left) + findKthSmallest(nums1, nums2, 0, 0, right)) / 2.0;
    }

    public int findKthSmallest(int[] nums1, int[] nums2, int s1, int s2, int k) {
        if (nums1.length == s1 || nums2.length == s2)
            return nums1.length == s1 ? nums2[s2+k-1] : nums1[s1+k-1];
        if (k == 1)
            return Math.min(nums1[s1], nums2[s2]);
        int loc1 = Math.min(nums1.length-1, s1 + k/2 - 1), loc2 = Math.min(nums2.length-1, s2 + k/2 -1);
        if (nums1[loc1] < nums2[loc2])
            return findKthSmallest(nums1, nums2, loc1+1, s2, k-loc1+s1-1);
        else
            return findKthSmallest(nums1, nums2, s1, loc2+1, k-loc2+s2-1);
    }*/

    // 三刷
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int left = (len1 + len2 + 1) / 2, right = (len1 + len2 + 2) / 2;
        return (findKthSmallest(nums1, nums2, 0, 0, left) + findKthSmallest(nums1, nums2, 0, 0, right)) / 2.0;
    }

    private double findKthSmallest(int[] nums1, int[] nums2, int s1, int s2, int k) {
        int len1 = nums1.length - s1, len2 = nums2.length- s2;
        if (s1 == nums1.length || s2 == nums2.length)
            return s1 == nums1.length ? nums2[s2 + k - 1] : nums1[s1 + k - 1];
        if (k == 1)
            return Math.min(nums1[s1], nums2[s2]);
        int loc1 = Math.min(nums1.length - 1, s1 + k/2 - 1), loc2 = Math.min(nums2.length - 1, s2 + k/2 - 1);
        return nums1[loc1] < nums2[loc2] ? findKthSmallest(nums1, nums2, loc1 + 1, s2, k - loc1 + s1 - 1) : findKthSmallest(nums1, nums2, s1, loc2 + 1, k - loc2 + s2 - 1);
    }
}